//#define _CRT_SECURE_NO_WARNINGS 1
//#include <stdio.h>
//#include <stdlib.h>
//#include <time.h>
//
//void MergeSort(int n, int* arr) {
//    if (n < 2) {
//        return;
//    }
//    int gap = 2;
//    int* rem = (int*)malloc(sizeof(int) * n);
//    while (gap / 2 <= n) {
//int i = 0;
//while (gap * i < n) {
//    int j = gap / 2;
//    int begin1 = gap * i;
//    int end1 = gap * i + j - 1;
//    int begin2 = gap * i + j;
//    int end2 = gap * (i + 1) - 1;
//
//    if (end1 >= n) {
//        end1 = n - 1;
//        begin2 = -1;
//        end2 = -2;
//    }
//    else if (begin2 >= n) {
//        begin2 = -1;
//        end2 = -2;
//    }
//    else if (end2 >= n) {
//        end2 = n - 1;
//    }
//
//    int m = begin1;
//    int n = begin2;
//    int y = begin1;
//    while (m <= end1 && n <= end2)
//    {
//        if (arr[m] <= arr[n]) {
//            rem[y++] = arr[m++];
//        }
//        else {
//            rem[y++] = arr[n++];
//        }
//    }
//    if (m > end1) {
//        while (n <= end2) {
//            rem[y++] = arr[n++];
//        }
//    }
//    else if (n > end2) {
//        while (m <= end1) {
//            rem[y++] = arr[m++];
//        }
//    }
//    i++;
//}
//gap *= 2;
//for (int i = 0; i < n; i++)
//{
//    arr[i] = rem[i];
//}
//    }
//    free(rem);
// }
//
// int main()
// {
//     int arr[10] = {0};
//     srand(time(NULL));
//     for (int j = 0; j < 10; j++)
//     {
//         for (int i = 0; i < 10; i++)
//         {
//             arr[i] = rand() % 100 + 1;
//         }
//         MergeSort(10, arr);
//         for (int i = 0; i < 10; i++)
//         {
//             printf("%d ", arr[i]);
//         }
//         printf("\n");
//     }
//     return 0;
// }